Social Big Data Mining by Ishikawa Hiroshi

Author:Ishikawa, Hiroshi [Ishikawa, Hiroshi]
Language: eng
Format: epub
Published: 2015-01-28T07:15:03+00:00

along the path connected with logical “AND” and the class represented

by the leaf node at the end of the path correspond to the precondition of a

classifi cation rule and the conclusion of the rule, respectively.

• The algorithm for induction of decision trees

The induction algorithm of the decision tree will be described below. It

is a basic algorithm called ID3 of Quinlan [Mitchell 1997, Han et al. 2001].

This algorithm assumes that category attributes are of a discrete type.

Therefore, if the algorithm is applied to a numerical attribute, it is necessary to discretize the attribute values as is the case in association rules.

(Algorithm) Decision tree induction

Input: Training data and attribute list

Output: Decision tree

1. Create a single node N for the samples in the training data;

2. If all the samples belong to the same class, let the node N be a leaf node and label the leaf node with the class name and terminate;

3. If the attribute list is empty, let the node N be a leaf node and label the leaf node with either a default class or the most common class and

terminate;

4. Select the test attribute by using a certain measure (e.g., information

gain) which can best divide samples into classes;

5. Label the node N with the selected test attribute;

6. Do the following procedure for each value a of the test attributes {

i

7.

Create a branch (test attribute = a ) from the node N;

i

8. Let

s be a subset of the sample data that satisfy the branch condition;

i

9. If S is empty, attach the branch to a leaf node that is labeled with i

either a default class or the most common class;

128 Social Big Data Mining

10.

Otherwise, let s and {the attribute list minus the test attribute} be

i,

new training data and a new attribute list, respectively, apply the

algorithm recursively, and attach to the branch the decision tree

returned as a result of the recursive application;};

8.4 Measure for Attribute Selection

Here, a measure used in selecting the appropriate attributes in the algorithm

for decision tree induction will be described. One of the frequently used

measures is a measure called information gain or entropy reduction. An

attribute that maximizes the value of the measure is selected as a test

attribute.

The samples S are assumed to consist of s sample pieces and each sample is assumed to consist of r attributes. The class attribute of the sample is assumed to have any class label representing the class C ( i = 1, m). C is i

i

assumed to contain s pieces as follows.

i

• S

= ∪ C , s =| S| , s = | C| ( i = 1 , m) i

i

i

The probability that a sample belongs to C is expressed as follows.

i

• p = s /s

i

i

The expected entropy is expressed by the following equation.

m

• I ( s , s ,..., s ) = −

p log p

1

2

m

∑ i 2 i

i=1

On the other hand, assuming that the attribute A has a distinctive value a j ( j = 1, v), S is alternatively expressed as follows.

• S

= ∪ S ( j = 1 , v)

j

Here S is a subset of S that satisfi es the condition that A = a .

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.